package com.xiaoyu.binaryTree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @program: DS_and_A
 * @description: 二叉树的层序遍历
 * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回其层序遍历结果：
 *
 * [
 *   [3],
 *   [9,20],
 *   [15,7]
 * ]
 *
 * 实现过程
 * 1、首先将二叉树的根节点push到队列中，判断队列不为NULL，就输出队头的元素，
 * 2、判断节点如果有孩子，就将孩子push到队列中，
 * 3、遍历过的节点出队列，
 * 4、循环以上操作，直到Tree == NULL。
 *
 * @author: YuWenYi
 * @create: 2021-05-19 10:17
 **/

/*
  普通的层次遍历这样就已经完成了
* if (root == null){
            return null;
        }
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode node;
        queue.offer(root);
        while (!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            node = queue.poll();
            list.add(node.val);
            if (node.left!=null){
                queue.offer(node.left);
            }
            if (node.right !=null){
                queue.offer(node.right);
            }
            res.add(list);
        }
        return res;
*
*
* */
public class LevelOrder_102 {
    //由于需要返回的结果是一个集合的集合,每一个小集合都是二叉树的一层,
    //因此我们不能按传统一次性只获取一个结点进行循环,而是需要一次性获取一层的结点,然后这样才能组合数据
    public static List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null){
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode node;
        queue.offer(root);
        while (!queue.isEmpty()){
            ArrayList<Integer> level = new ArrayList<>();
            int currentSize = queue.size();
            //通过这个循环,一次性获取一层的结点
            for (int i = 1; i <= currentSize; i++) {
                node = queue.poll();
                level.add(node.val);
                if (node.left!=null){
                    queue.offer(node.left);
                }
                if (node.right !=null){
                    queue.offer(node.right);
                }
            }
            res.add(level);
        }
        return res;
    }


    public static void simpleLevelOrder(TreeNode root){
        if (root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode node;
        queue.offer(root);
        while (!queue.isEmpty()){
            node = queue.poll();
            System.out.print(node.val+" ");
            if (node.left!=null){
                queue.offer(node.left);
            }
            if (node.right !=null){
                queue.offer(node.right);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode right = new TreeNode(3,new TreeNode(4),new TreeNode(5));
        TreeNode left = new TreeNode(2,new TreeNode(6),new TreeNode(7));
        TreeNode root = new TreeNode(1,left,right);
        List<List<Integer>> lists = levelOrder(root);
        System.out.println(lists);
        simpleLevelOrder(root);

    }
}
